The present invention relates generally to decompressing graphics data, and more particularly to methods and apparatuses that decompress compressed three-dimensional geometry data.
Modem three-dimensional computer graphics use geometry extensively to describe three-dimensional objects, using a variety of graphical representation techniques. Computer graphics find wide use in applications ranging from computer assisted design (xe2x80x9cCADxe2x80x9d) programs to virtual reality video games. Complex smooth surfaces of objects can be succinctly represented by high level abstractions such as trimmed non-uniform rational splines (xe2x80x9cNURBsxe2x80x9d), and often detailed surface geometry can be rendered using texture maps. But adding more realism requires raw geometry, usually in the form of triangles. Position, color, and normal components of these triangles are typically represented as floating point numbers, and describing an isolated triangle can require upwards of 100 bytes of storage space.
Understandably, substantial space is necessary for three-dimensional computer graphics objects to be stored, e.g., on a computer hard disk or compact disk read-only memory (xe2x80x9cCD-ROMxe2x80x9d). Similarly, considerable time in necessary for such objects to be transmitted, e.g., over a network, or from disk to main memory.
Geometry compression is a general space-time trade-off, and offers advantages at every level of a memory/interconnect hierarchy. A similar systems problem exists for storage and transmission of two-dimensional pixel images. A variety of lossy and lossless compression and decompression techniques have been developed for two-dimensional pixel images, with resultant decrease in storage space and transmission time. Unfortunately, the prior art does not include compression/decompression techniques appropriate for three-dimensional geometry, beyond polygon reduction techniques. However, the Ph.D. thesis entitled Compressing the X Graphics Protocol by John Danskin, Princeton University, 1994 describes compression for two-dimensional geometry.
Suitable compression can greatly increase the amount of geometry that can be cached, or stored, in the fast main memory of a computer system. In distributed networked applications, compression can help make shared virtual reality (xe2x80x9cVRxe2x80x9d) display environments feasible, by greatly reducing transmission time.
Most major machine computer aided design (xe2x80x9cMCADxe2x80x9d) software packages, and many animation modeling packages use constructive solid geometry (xe2x80x9cCSGxe2x80x9d) and free-form NURBS to construct and represent geometry. Using such techniques, regions of smooth surfaces are represented to a high level with resulting trimmed polynomial surfaces. For hardware rendering, these surfaces typically are pre-tessellated in triangles using software before transmission to rendering hardware. Such software pre-tessellation is done even on hardware that supports some form of hardware NURBS rendering.
However, many advantages associated with NURBS geometric representation are for tasks other than real-time rendering. These non-rendering tasks include representation for machining, interchange, and physical analysis such as simulation of turbulence flow. Accurately representing trimming curves for NURBS is very data intensive, and as a compression technique, trimmed NURBS can not be much more compact than pre-tessellated triangles, at least at typical rendering tessellation densities. Finally, not all objects are compactly represented by NURBS. Although many mechanical objects such as automobile hoods and jet turbine blades have large, smooth areas where NURBS representations can be advantageous, many objects do not have such areas and do not lend themselves to such representation. Thus, while NURBS will have many applications in modelling objects, compressed triangles will be far more compact for many classes of application objects.
Photo-realistic batch rendering has long made extensive use of texture map techniques to compactly represent fine geometric detail. Such techniques can include color texture maps, normal bump maps, and displacement maps. Texture mapping works quite well for large objects in the far background, e.g., clouds in the sky, buildings in the distance. At closer distances, textures work best for three-dimensional objects that are mostly flat, e.g., billboards, paintings, carpets, marble walls, and the like. More recently, rendering hardware has begun to support texture mapping, and real-time rendering engines can also apply these techniques.
However, texture mapping results in a noticeable loss of quality for nearby objects that are not flat. One partial solution is the xe2x80x9csignboardxe2x80x9d, in which a textured polygon always swivels to face the observer. But when viewed in stereo, especially head-tracked VR stereo, nearby textures are plainly perceived as flat. In these instances, even a lower detail but fully three-dimensional polygonal representation of a nearby object would be much more realistic.
Polyhedral representation of geometry has long been supported in the field of three-dimensional raster computer graphics. In such representation, arbitrary geometry is expressed and specified typically by a list of vertices, edges, and faces. As noted by J. Foley, et al. in Computer Graphics: Principles and Practice, 2nd ed., Addison-Wesley, 1990, such representations as winged-edge data structures were designed as much to support editing of the geometry as display. Vestiges of these representations survive today as interchange formats, e.g., Wavefront OBJ. While theoretically compact, some compaction is sacrificed for readability by using ASCII data representation in interchange files. Unfortunately, few if any of these formats can be directly passed as drawing instructions to rendering hardware.
Another historical vestige in such formats is the support of N-sided polygons, a general primitive form that early rendering hardware could accept. However, present day faster rendering hardware mandates that all polygon geometry be reduced to triangles before being submitted to hardware. Polygons with more than three sides cannot in general be guaranteed to be either planar or convex. If quadrilaterals are accepted as rendering primitives, it is to be accepted that they will be arbitrarily split into a pair of triangles before rendering.
Modem graphics languages typically specify binary formats for the representation of collections of three-dimensional triangles, usually as arrays of vertex data structures. Thus, PHIGS PLUS, PEX, XGL, and proposed extensions to OpenGL are of this format form, and will define the storage space taken by executable geometry.
It is known in the art to isolate or chain triangles in xe2x80x9czigzagxe2x80x9d or xe2x80x9cstarxe2x80x9d strips. For example, Iris-GL, XGL, and PEX 5.2 define a form of generalized triangle strip that can switch from a zigzag to star-like vertex chaining on a vertex-by-vertex basis, but at the expense of an extra header word per vertex in XGL and PEX. A restart code allows multiple disconnected strips of triangles to be specified within one array of vertices.
In these languages, all vertex components (positions, colors, normals) may be specified by 32-bit single precision IEEE floating point numbers, or 64-bit double precision numbers. The XGL, IrisGL, and OpenGL formats also provide some 32-bit integer support. The IrisGL and OpenGL formats support vertex position component inputs as 16-bit integers, and normals and colors can be any of these as well as 8-bit components. In practice, positions, colors, and normals can be quantized to significantly fewer than 32 bits (single precision IEEE floating point) with little loss in visual quality. Such bit-shaving may be utilized in commercial three-dimensional graphics hardware, providing there is appropriate numerical analysis support.
However compressed, geometric data including three-dimensional geometry data must be decompressed to be useful. For example, applicant""s patent application Ser. No. 08/511,294 filed Aug. 4, 1995, entitled METHOD AND APPARATUS FOR GEOMETRIC COMPRESSION OF THREE-DIMENSIONAL GRAPHICS DATA, assigned to the assignee herein, discloses such compression.
Thus, there is a need for method and apparatus for decompressing three-dimensional geometry that has been compressed. Preferably, decompression is such that the output data may be passed to rendering hardware directly as drawing instructions. Finally, decompression of three-dimensional geometry should be implementable using hardware, software, or a combination thereof.
The present invention discloses such decompression.
For decompression according to the present invention, three-dimensional geometry is first represented as a generalized triangle mesh, which allows each instance of a vertex in a linear stream to specify an average of between ⅓ triangle and 2 triangles. Individual positions, colors, and normals are quantized, with a variable length compression being applied to individual positions, colors, and normals. Quantized values are delta-compression encoded between neighbors to provide vertex traversal orders, and mesh buffer references are created. Histograms of delta-positions, delta-normals and delta-colors are created, after which variable length Huffman tag codes, as well as delta-positions, delta-normals and delta-colors are created. The compressed output binary stream includes the output Huffman table initializations, ordered vertex traversals, output tags, and the delta-positions, delta-normals, and delta-colors.
Decompression of such compressed three-dimensional geometry data may be implemented in hardware, software, or a combination of each. The decompression unit includes an input FIFO that receives compressed data bits and a signal noting size of the incoming data. The FIFO outputs are coupled to an input block state machine and an input block. Outputs from the input block and input block state machine are coupled to a barrel shifter unit. Input block output also is input to Huffman tables that output to the state machine. The state machine output also is coupled to a data path controller whose output is coupled to a tag decoder, and to a normal processor receiving output from the barrel shifter unit. The decompressor unit also includes a position/color processor that receives output from the barrel shifter unit. Outputs from the normal processor and position/color processor are multiplexed to a format converter.
For instructions in the data stream that generate output to the format converter, the decompression unit generates a 12-bit tag that is sent to the tag decoder in parallel with bits for normals that are sent to the format converter. A read-back path is used to read back the internal state of the decompressor unit. The decompressor unit carries out the following procedures:
(1) Fetch the rest of the next instruction, and the first 8 bits of the following instruction;
(2) Using the tag table, expand any compressed value fields to full precision;
(3A) If values are relative, add to current value; otherwise replace;
(3B) If mesh buffer reference, access old values;
(3C) If other command, do housekeeping;
(4) If normal, pass index through ROM table to obtain full values;
(5) Output values in generalized triangle strip form to next stage.
The decompressed stream of triangle data may then be passed to a traditional rendering pipeline, where it can be processed in full floating point accuracy, and thereafter displayed or otherwise used.